package middle;

import java.util.*;

/**
 * 17.电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 示例:
 *
 * 输入："23"
 * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 *
 *
 * */
public class LetterCombinations {
    List<String> results = new ArrayList<>();
    // 字母组合 回溯法
    public void combinations(String combination, String next_digits){

        HashMap<String,String> hashMap = new HashMap<String, String>(){{
            put("2","abc");
            put("3","def");
            put("4","ghi");
            put("5","jkl");
            put("6","mno");
            put("7","pqrs");
            put("8","tuv");
            put("9","wxyz");
        }};

        // 判断还有没有数字 如果没有就将组合字母加入到结果集中
        if(next_digits.length() == 0){
            results.add(combination);
        }else{
            // 获取数字 然后获取数字对应的字母串
            String digit = next_digits.substring(0, 1);
            String letters = hashMap.get(digit);
            for (int i = 0; i < letters.length(); i++) {
                String letter = hashMap.get(digit).substring(i, i + 1);
                // append the current letter to the combination
                // and proceed to the next digits
                combinations(combination + letter, next_digits.substring(1));
            }
        }

    }

    // 利用队列解法
    public List<String> solve(String digits){
        if(digits.length() == 0){
            return new ArrayList<>();
        }

        String[] letter_map = {
                " ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
        };
        // 这里我们用List模拟队列的排队和出队即可,直接返回队列即可
        List<String> queue = new ArrayList<>();
        // 先加入一个空字符串方便和第一个字母串进行组合
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            // 取出第一个数字所对应的字母串
            String letters = letter_map[digits.charAt(i) - '0'];
            // 记录一下队列的长度
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                // 每次都将队列的第一个元素拿出来和接下来的字母串进行组合
                String tmp = queue.remove(0);
                for (int k = 0; k < letters.length(); k++) {
                    queue.add(tmp + letters.charAt(k));
                }
            }
        }
        return queue;
    }

    // main
    public static void main(String[] args) {
        LetterCombinations l = new LetterCombinations();
        List<String> s =  l.solve("23");
        System.out.println(Arrays.toString(s.toArray()));
    }
}
